#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    """
    @param: nums: A list of integers.
    @return: A list of permutations.
    """
    def permute(self, nums):
        self.ret = []
        self.rec_permute(nums, [])
        return self.ret

    def rec_permute(self, nums, path):
        # 效率并不算太好: 因为大量copy nums, path, pop
        l = len(nums)
        if not nums:
            self.ret.append(path)
            return

        for i in range(l):
            new_nums = list(nums)
            new_path = list(path)
            # print(new_nums)
            v = new_nums.pop(i)
            new_path.append(v)
            self.rec_permute(new_nums, new_path)


def main():
    print("start main")
    s = Solution()
    ret = s.permute([1,2,3])
    print(ret)


if __name__ == "__main__":
    main()
